package 排序;

import java.util.*;

public class Sort {
    public static void main(String[] args) {
        int[] arr1 = {3, 5, 6, 2, 7, 9, 8, 0};
//        mergeSort(arr1,0,7);//归并排序
//        quickSort(arr1, 0, 7);//快速排序
        CountSort(arr1);//计数排序
        RadixSort(arr1);//基数排序

//        BucketSort(arr1,4);//桶排序
        System.out.println("原始数组为：" + Arrays.toString(arr1));
//        System.out.println(Arrays.toString(arr2));
    }

    /**
     * 冒泡排序
     *
     * @param arr
     * @return
     */
    public static int[] BubbleSort(int[] arr) {
        //数组为空或者长度为0时
        if (arr == null || arr.length == 0) {
            return null;
        }
        for (int i = 0; i < arr.length; i++) {//外层循环为比较的次数
            for (int j = 0; j < arr.length - 1 - i; j++) {//内层循环为每一层查找
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }

    /**
     * 选择排序
     *
     * @param arr
     * @return
     */
    public static int[] SelectSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        for (int i = 0; i < arr.length; i++) {//外层循环
            int key = i;//初始化最小值索引
            for (int j = i; j < arr.length; j++) {
                if (arr[key] > arr[j]) {//找到更小的，记录最小索引
                    key = j;
                }
            }
            if (key != i) {//有更小的，交换
                int temp = arr[key];
                arr[key] = arr[i];
                arr[i] = temp;
            }

        }
        return arr;
    }

    /**
     * 插入排序
     *
     * @param arr
     * @return
     */
    public static int[] InsertSort(int[] arr) {
        //升序排列
        //空数组或没有数据
        if (arr == null || arr.length == 0) {
            return null;
        }
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];//要排序的值
            int j = i - 1;//从要排序的元素前一个开始找起
            while (j >= 0 && arr[j] > key) {//在范围内要排序的值比当前值大
                arr[j + 1] = arr[j];//后移一位
                j--;//下表前移
            }
            //直到最后不能前移，剩下的空位时第j+1
            arr[j + 1] = key;
        }
        return arr;
    }

    /**
     * 希尔排序
     *
     * @param arr
     * @return
     */
    public static int[] shellSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        int n = arr.length;
        // 初始化间隔（gap）的值，它决定了每次迭代中子数组的大小
        // 从数组长度的一半开始作为初始间隔值，gap就是分割的子数组数量
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 循环从间隔值开始，遍历数组直到数组的末尾；代表循环所有的子数组
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;
                // 将当前元素 arr[j] 的值替换为前一个元素 arr[j - gap] 的值。
                // 通过这个操作，将较大的元素向后移动，为当前元素腾出位置
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
        return arr;
    }

    /**
     * 归并排序
     *
     * @param arr
     * @param left
     * @param right
     */
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);//合并已经排好序的两个数组
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;//左子树长度
        int n2 = right - mid;//右子树长度
        //创建两个临时数组
        int[] L = new int[n1];
        int[] R = new int[n2];
        //赋值
        for (int i = 0; i < n1; i++) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid + 1 + j];
        }
        //使用三个变量分别指向数组L，R，arr的起始位置
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {//两个数组都还不为空
            if (L[i] <= R[j]) {//L[i]比较小
                arr[k] = L[i];
                i++;
            } else {//R[j]比较小
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        while (i < n1) {//L数组还没用完
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {//R数组还没用完
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    /**
     * 快速排序
     *
     * @param arr
     * @param left
     * @param right
     */
    // 接收一个数组 arr，一个左索引 left ，和一个右索引 right 作为参数
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivot = partition(arr, left, right);
            quickSort(arr, left, pivot - 1);
            quickSort(arr, pivot + 1, right);
        }
    }

    /**
     * 找一个元素作为基准数，较小的元素放在它的左边，较大的元素放在它的右边
     *
     * @param arr   输入数组
     * @param left  左索引
     * @param right 右索引
     * @return
     */
    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];//取第一个元素作为基值
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                // 如果当前元素 arr[j] 小于枢轴元素，则增加 i 并交换 arr[i] 和 arr[j]
                // 较小元素索引+1
                i++;
                // 将当前元素 arr[j] 放在较小元素索引位置
                // 将较小元素放在前面
                swap(arr, i, j);
            }
            // 其他情况，则较小元素索引没有增加，说明当前元素应该放在右边
        }
        // 将枢轴元素（ arr[high] ）与索引 i + 1 处的元素交换。
        // 确保枢轴元素左边是较小元素，右边是较大元素
        swap(arr, i + 1, right);
        // 将 i + 1 作为枢轴索引返回
        return i + 1;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 堆排序
     *
     * @param arr
     */
    public static void HeapSort(int[] arr) {
        int arrLength = arr.length;
        for (int i = arr.length - 1; i > 0; i--) {
            initHeap(arr, arrLength);//堆排序
            swap(arr, i, 0);//交换
            arrLength--;
        }
    }

    private static void initHeap(int[] arr, int arrLength) {
        boolean hasTwoChild = (arrLength % 2) == 1 ? true : false;//判断最后一个子节点是否为双分支
        for (int i = (arrLength - 2) >> 1; i >= 0; i--) {
            if (hasTwoChild) {
                if (arr[(i * 2) + 2] > arr[i] && arr[(i * 2) + 2] >= arr[(i * 2) + 1]) {
                    swap(arr, (i * 2) + 2, i);//交换节点
                    downAdjust(arr, (i * 2) + 2, arrLength);//下沉
                } else if (arr[(i * 2) + 1] > arr[i] && arr[(i * 2) + 1] > arr[(i * 2) + 2]) {
                    swap(arr, (i * 2) + 1, i);
                    downAdjust(arr, (i * 2) + 1, i);
                }
            } else {
                if (arr[(i * 2) + 1] > arr[i]) {
                    swap(arr, (i * 2) + 1, i);
                }
                hasTwoChild = true;
            }
        }

    }

    //向下调整
    private static void downAdjust(int[] arr, int index, int arrLength) {
        if (index > (arrLength - 2) >> 1) {
            return;
        } else if ((index * 2) + 2 >= arrLength) {
            if (arr[(index * 2) + 1] > arr[index]) {
                swap(arr, (index * 2) + 1, index);
            }
        } else {
            if (arr[(index * 2) + 2] > arr[index] && arr[(index * 2) + 2] >= arr[(index * 2) + 1]) {
                swap(arr, (index * 2) + 2, index);
                downAdjust(arr, (index * 2) + 2, index);
            } else if (arr[(index * 2) + 1] > arr[index] && arr[(index * 2) + 1] >= arr[(index * 2) + 2]) {
                swap(arr, (index * 2) + 1, index);
                downAdjust(arr, (index * 2) + 1, index);
            }
        }
    }

    /**
     * 桶排序
     *
     * @param arr
     * @param bucketNum
     */
    public static void BucketSort(int[] arr, int bucketNum) {
        //传入数组和桶的数量
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i : arr) {
            max = Math.max(max, i);
            min = Math.min(min, i);
        }
        List<List<Integer>> bucketList = new ArrayList<List<Integer>>();
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new ArrayList<>());
        }
        for (int i : arr) {
            int bucketIndex = (i - min) * (bucketNum - 1) / (max - min);//找到要放的桶
            List<Integer> list = bucketList.get(bucketIndex);//获取桶
            list.add(i);//添加元素
        }
        for (int i = 0, arrIndex = 0; i < bucketList.size(); i++) {
            List<Integer> bucket = bucketList.get(i);//遍历桶
            Collections.sort(bucket);//桶内排序
            for (int num : bucket) {//遍历赋值给原数组
                arr[arrIndex++] = num;
            }
        }
    }

    /**
     * 计数排序
     *
     * @param arr
     */
    public static void CountSort(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i : arr) {//找最大值
            max = Math.max(max, i);
        }
        int[] countArr = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i]]++;//计数
        }
        int arrIndex = 0;
        for (int i = 0; i < countArr.length; i++) {
            for (int j = 0; j < countArr[i]; j++) {
                arr[arrIndex++] = i;
            }
        }
    }

    /**
     * 基数排序
     *
     * @param arr
     */
    public static void RadixSort(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i : arr) {//找最大值
            max = Math.max(max, i);
        }
        int maxLength = String.valueOf(max).length();
        LinkedList<Integer>[] radixList = new LinkedList[10];
        for(int i=0;i<radixList.length;i++){
            radixList[i]=new LinkedList<Integer>();
        }
        for (int i = 0; i < maxLength; i++) {
            for (int j = 0; j < arr.length; j++) {
                radixList[getRadix(arr[j], i)].add(arr[j]);
            }
            int index=0;
            for(int j=0;j<radixList.length;j++){
                while(radixList[j].isEmpty()==false){
                    arr[index++]=radixList[j].remove();
                }
            }
        }
    }

    private static int getRadix(int num, int pos) {
        int result = 0;
        for(int i=1;i<=pos;i++){
            result = num%10;
            num/=10;
        }
        return result;
    }
}
